The present invention relates to computer-based scheduling of complex technical tasks in a control system, and in particular to determine in a control system an ordering for a set of complex tasks that have multiple attributes according to a single ordering criterion that takes into account plurality of the attributes.
There is often a need to schedule complex processes that includes a large set of tasks. For example, in a complex processing plant there may be a need to schedule and manage a large number of technical tasks. The technical tasks have multiple attributes, e.g., attributes that are definable by a numeric quantity. A computerized control system may be involved in assigning these tasks to one or more task performing entities of the plant. Such a computerized control system may include a data structure, e.g., a database in which each task is represented by a record. Each task's attributed can be represented by different fields in the records.
In such a control system, there is often a need to determine the ordering of the tasks, e.g., which task is to be performed next. There also may be a need for the control system to display the ordering of the tasks on a display device so that a human user can view the ordering. To determine such ordering, it is well known to assign a key, e.g., a sort key to each record when designing the database, and for the control system to sort the records according to the sort key. If the tasks in the control system are represented by records having fields, one of the fields is typically designated as the sort field. Other fields also may be assigned as sort fields, e.g., as secondary sort fields.
In many situations it is difficult for the control system to determine which field makes the most useful primary sort field, which is the most useful secondary sort field etc. For example, suppose the control system is to control performing a set of tasks that relate to safety. Suppose on the fields is an indication of the importance of the task as it related to safety, and another of fields is an indication of the time remaining until the task has to be completed else safety is affected. Suppose the control system is to schedule performing of the tasks as to which is to be performed first, which second, etc. Which is the primary sort field? If the sort is performed according to importance, one or more record representing tasks that are due within a short period of time might be placed towards the end of the sorted set simply because the tasks due within the short period happen not to be very important. Hence this fails to produce a sort order that corresponds to the sequence in which the tasks should be scheduled by the control system to be performed. On the other hand, for the control system to sort by when completion is required also may produces undesirable results. A task of critical importance might now be scheduled towards the end of the sorted set because it is not due for time. Also, the completion period is not accounted for.
Thus, there is a need in the art for a method and for a control system that can schedule tasks according to a single criterion e.g., a single sort key determined by a combination of attributes.
The prior art includes U.S. Pat. No. 6,738,769; to Sharp that describes sorting multiple-typed data, U.S. Pat. No. 3,593,309; to Clark et al. that describes a method and means for generating compressed keys; U.S. Pat. No. 3,602,895 to Loizides that describes a one key byte per key indexing method and means therefor; U.S. Pat. No. 4,209,845 to Berger, et al. that describes a file qualifying and sorting system; U.S. Pat. No. 4,417,321 to Chang, et al. that describes qualifying and sorting file record data; U.S. Pat. No. 4,499,555 to Huang that describes a sorting technique; U.S. Pat. No. 4,559,612 to Vrielink that describes a sorting device for data words; U.S. Pat. No. 4,567,572 to Morris et al. that describes a fast parallel sorting processor; U.S. Pat. No. 4,595,995 to Alles that describes a sort circuit and a method using multiple parallel sorts of the sorted items; and U.S. Pat. No. 4,628,483 to Nelson that describes a one level sorting network.
FIG. 1 shows a flowchart of a typical prior art sorting method that can be incorporated in a computerized control system for scheduling tasks, the method operating on a set of data objects, which, in one example, are database records. Typically, in 10, the user first selects the set of data objects, e.g., records to be sorted and in 20 selects the fields containing the values on which the ordering is based. The sorting method in 30 generates the relevant collation keys for each selected field in the selected records and proceeds in 40 to sort these collation keys. Once the collation keys have been sorted, the method in 50 produces the relevant output, e.g., in the case of tables of a database, using the row indices associated with the now-ordered collation keys.
According to such prior art methods, the step 10 of selecting sort fields also determines a priority order among the sort fields. This order is used as a tiebreaker in the event that at least two collation keys are equivalent, a situation that would otherwise result in only a partial ordering. This process is illustrated in FIG. 2, which shows in simplified form a flowchart of collation key comparison in a typical prior art sort method. If (in 80) at least two data objects have the same value in the primary sort field, the method in 90 compares the secondary sort fields. If the secondary sort field values are again equivalent and it is still not possible to order the two data objects, the method in 90 compares the tertiary sort fields, and so on. In some—possible many—cases, only a partial ordering will be possible.
As discussed above, one limitation of such a prior art method is that no attempt is made to account for the degree to which individual data objects are “relevant” to the user and/or the user's operating context, where operating context refers to the circumstances within which the sort operation is executed, including one or more of the state of to-be-sorted data objects in memory (temporary or permanent), which files are currently open, which records are currently being viewed or being input, the identity, preference settings and/or the security profile of the user and of other users or system with which the user is conducting an electronic transaction. By the term “relevance” is included the degree to which a data object has priority in the case of scheduling tasks, or the like.
Clearly it would be better not to force the user to scan through a large amount of what the user might consider information of low relevance, to pick out the subset of items he/she actually wishes to devote attention to at a given point in time. Thus there is a need in the art for a sorting method that takes into account a measure of relevance to the user and/or the user's operating context. There also is a need in the art to determine such a measure of relevance or context on which to base the sorting.
Another problem in prior art methods is a result of the prior art methods ordering records taking a single measure of relevance into account, the measure a function of a plurality of sort fields. In such, it is necessary to always produce the list of all possible records, since it cannot be guaranteed that items in the latter part of the list are less relevant to the user than those in the earlier part. This increases the risk of what we call “information overload.”
Thus, prior art methods can predispose the user to loose sight of important information items among items of lesser relevance, to waste time reading irrelevant material and to waste paper in unnecessarily long print-outs. All this according to a measure of “relevance.”
Thus, there is a need in the art for sorting methods that can restrict the sorting to only the most relevant data objects of a set of data objects.
Frequently, within a set of data objects, there emerge natural relationships between individual data objects, such that some data objects are more closely related to each other than are other data objects. Simply sorting data objects according to the value in a particular field or to values in a set of fields does not guarantee that related objects will be reproduced in close proximity in the results list. This causes a user viewing the results to need to jump from one place in the sorted list to another to get a comprehensive view of a set of related data objects. Such viewing can be a complex and error prone process; the user is often unsure whether all related items have been viewed, and where the next related item is located.
Thus there is a need in the art for a sorting method that orders closely related data objects close to each other.